package org.xingole.leetcode.dp.grid;

public class KnightProbabilityInChessboard {
    public double knightProbability(int n, int k, int row, int column) {
        /*
         * We can reduce our problem to finding the probability of the knight being on
         * the board after k moves equals the sum of probabilities of being in the cell
         * (i, j) over all 0 <= i < n, 0 <= j < n.
         * 
         * Where the knight locates at the kth move depends on where it was at the previous
         * (k-1)th move which in turn depends on where it was at the (k-2)th move and so
         * on.
         * 
         * 1. Let's think about what we need to completely describe the knight's state.
         * 
         * The knight makes the first move, then the second one, the third one, and so on
         * until the last kth move. The first parameter that describes the state is moves -
         * how many moves has the knight already made.
         * 
         * Also we need the knight's location on the chessboard, which we can describe with
         * two integers i and j - the cell's coordinates.
         * 
         * 2, To solve the problem using dynamic programming, we define dp[moves][i][j] as the
         * probability of the knight being at cell (i, j) on the chessboard after moves moves.
         * 
         * The base case is when moves = 0, representing the starting position of the knight.
         * In this case, the probability of being at cell (row, column) is 100%. We set
         * dp[0][row][column] = 1, and all other cells have a probability of 0.
         * 
         * For a given cell (i, j), we iterate over the possible directions, calculating the
         * probability of reaching cell (i, j) from neighboring cells (i', j') in the previous
         * move. The variables i' and j' represent the coordinates of neighboring cells (in
         * the sense of knight's moves).
         * 
         * By considering all possible directions and summing up the probabilities from the
         * neighboring cells and divide the result by 8 since there are eight possible moves
         * for the knight.
         * 
         * dp[moves][i][j] = 1/8 * sum(dp[moves - 1][i'][j'])
         */

        // Define possible directions for the knight's moves
        int[][] directions = {
            {1, 2}, {1, -2}, {-1, 2}, {-1, -2},
            {2, 1}, {2, -1}, {-2, 1}, {-2, -1}
        };

        // Initialize the dynamic programming table
        double[][][] dp = new double[k + 1][n][n];
        dp[0][row][column] = 1.0;

        // Iterate over the number of moves
        for (int moves = 1; moves <= k; moves++) {
            // Iterate over the cells on the chessboard
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // Iterate over the cells on the chessboard
                    for (int[] direction : directions) {
                        int prevI = i - direction[0];
                        int prevJ = j - direction[1];

                        // Check if the previous cell is within the chessboard
                        if (prevI >= 0 && prevI < n && prevJ >= 0 && prevJ < n) {
                            // Add the previous probability divided by 8
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8.0;
                        }
                    }
                }
            }
        }

        // Calculate total probability by summing probabilities for all cells
        double totalProbability = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalProbability += dp[k][i][j];
            }
        }

        return totalProbability;
    }
}
